#pragma once
#include <iostream>
#include <vector>
#include <list>
using namespace std;


struct Uint3
{
	unsigned int num : 3;
};

template<class graph_type>
class PathTable
{
private:
	vector<vector<short>> pathTable;

public:
	PathTable() {};
	PathTable(const graph_type& G) {CreateTable(G);};
	~PathTable() {};

	void CreateTable(const graph_type& G);
	list<int> GetPath(int nod1, int nod2);
};


template <class graph_type>
void PathTable<graph_type>::CreateTable(const graph_type& G)
{
  enum {no_path = -1};
  
  std::vector<Uint8> row(G.NumNodes(), no_path);
  
  std::vector<std::vector<short> > ShortestPaths(G.NumNodes(), row);

  for (int source=0; source<G.NumNodes(); ++source)
  {
    //calculate the SPT for this node

	  if(G.m_Edges[source].empty())
		  continue;
    Graph_SearchDijkstra<graph_type> search(G, source);

    std::vector<const graph_type::EdgeType*> spt = search.GetSPT();

    //now we have the SPT it's easy to work backwards through it to find
    //the shortest paths from each node to this source node
    for (int target = 0; target<G.NumNodes(); ++target)
    {
      //if the source node is the same as the target just set to target
      if (source == target)
	  {
        ShortestPaths[source][target] = target;
      }

      else
      {
        int nd = target;

        while ((nd != source) && (spt[nd] != 0))
        {
          ShortestPaths[spt[nd]->From()][target]= nd;

          nd = spt[nd]->From();
        }
      }
    }//next target node
  }//next source node

  pathTable = ShortestPaths;
}

template <class graph_type>
list<int> PathTable<graph_type>::GetPath(int start, int dest)
{
	list<int> path;
	int currNode = start;
	while(currNode != dest)
	{
		path.push_back(currNode);
		currNode = pathTable[currNode][dest];
	}

	return path;
}

